#include <vector>
using std::endl;
using std::cout;
using std::vector;

//闭散列的哈希表
namespace CloseHash 
{
	//在线性探测中的删除 不能直接移除数据 否则会默认同样映射的值不在表中  hash函数为%10  
	//在删除4 时  14也是去4的位置找 发现当前没有值 就说明没有4这个映射 也就认为没有14
	enum State {
		EXIST,
		DELETE,
		EMPTY
	};
	//需要将State作为成员封装到哈希数据中 
	template<class K ,class V>
	class HashDate 
	{
	public:
		std::pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K,class V>
	class HashTable
	{
	public:
		bool Insert(const std::pair<K, V>& kv)
		{
			if(Find(kv.first)) return false;
			//开始插入之间 先看看空间够不够
			if(_tables.empty() || 10 * _size / _tables.size() >= 7)
			{
				Expand();
			}
			//扩容完成 或者空间够大
			//1.使用哈希函数计算映射下标
			size_t hashi = kv.first % _tables.size();
			//负数也无所谓  无符号%有符号 会发生整形提升 全都提升成了无符号数 负数也会存在映射
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			_size++;
			return true;
		}
		void Expand()
		{
			//扩容
			int newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			HashTable<K, V> newHash;
			newHash._tables.resize(newsize);
			for (auto& e : _tables)
			{
				if (e._state == EXIST)
				{
					newHash.Insert(e._kv);
				}
			}
			_tables.swap(newHash._tables);
		}

		HashDate<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0) return nullptr;
			size_t hashi = key % _tables.size();
			size_t start = hashi;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key && _tables[hashi]._state != DELETE)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
				if (hashi == start)
				{
					break;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashDate<K, V>*ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._state == EXIST)
				{
					printf("[%d:%d] ", i, _tables[i]._kv.first);
				}
				else
				{
					printf("[%d:*] ", i);
				}
			}
			cout << endl;
		}


	private:
		vector<HashDate<K, V>> _tables;
		size_t _size = 0;
	};

}